﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.Serialization;
using System.Threading;
using System.Xml.Serialization;
using MugenMvvmToolkit.Utils;

namespace MugenMvvmToolkit.Infrastructure
{
    /// <summary>
    ///     Represents a collection of key/value pairs that are sorted by key based on the associated
    ///     <see
    ///         cref="T:System.Collections.Generic.IComparer`1" />
    ///     implementation.
    /// </summary>
    /// <typeparam name="TKey">
    ///     The type of keys in the collection.
    /// </typeparam>
    /// <typeparam name="TValue">
    ///     The type of values in the collection.
    /// </typeparam>    
#if WPF
    [Serializable]
#endif
    [DebuggerDisplay("Count = {Count}")]
    [DataContract(IsReference = true)]
    internal sealed class OrderedListInternal<TKey, TValue>
    {
        #region Fields

        private static readonly TKey[] EmptyKeys = new TKey[0];
        private static readonly TValue[] EmptyValues = new TValue[0];
        private readonly IComparer<TKey> _comparer;
        private TKey[] _keys;
        private int _size;
        private TValue[] _values;

        #endregion

        #region Constructors

        /// <summary>
        ///     Initializes a new instance of the <see cref="OrderedListInternal{TKey,TValue}" /> class that is empty, has the default initial capacity, and uses the default
        ///     <see
        ///         cref="T:System.Collections.Generic.IComparer`1" />
        ///     .
        /// </summary>
        public OrderedListInternal()
        {
            _keys = EmptyKeys;
            _values = EmptyValues;
            _size = 0;
            _comparer = Comparer<TKey>.Default;
        }

        #endregion

        #region Properties

        /// <summary>
        ///     Gets or sets the number of elements that the <see cref="OrderedListInternal{TKey,TValue}" /> can contain.
        /// </summary>
        public int Capacity
        {
            get { return _keys.Length; }
            set
            {
                if (value == _keys.Length)
                    return;
                if (value < _size)
                    Thrower.CapacityLessThanCollection("Capacity");
                if (value > 0)
                {
                    var keyArray = new TKey[value];
                    var objArray = new TValue[value];
                    if (_size > 0)
                    {
                        Array.Copy(_keys, 0, keyArray, 0, _size);
                        Array.Copy(_values, 0, objArray, 0, _size);
                    }
                    _keys = keyArray;
                    _values = objArray;
                }
                else
                {
                    _keys = EmptyKeys;
                    _values = EmptyValues;
                }
            }
        }

        /// <summary>
        ///     Gets a collection containing the keys in the <see cref="OrderedListInternal{TKey,TValue}" />.
        /// </summary>
        public TKey[] Keys
        {
            get { return _keys; }
        }

        /// <summary>
        ///     Gets a collection containing the values in the <see cref="OrderedListInternal{TKey,TValue}" />.
        /// </summary>
        public TValue[] Values
        {
            get { return _values; }
        }

        /// <summary>
        ///     Gets the number of key/value pairs contained in the <see cref="OrderedListInternal{TKey,TValue}" />.
        /// </summary>
        public int Count
        {
            get { return _size; }
        }

        #endregion

        #region Methods

        /// <summary>
        ///     Adds an element with the specified key and value into the <see cref="OrderedListInternal{TKey,TValue}" />.
        /// </summary>
        public int Add(TKey key, TValue value)
        {
            Should.NotBeNull(key, "key");
            int num = Array.BinarySearch(_keys, 0, _size, key, _comparer);
            if (num >= 0)
                Thrower.DuplicateItemCollection();
            return Insert(~num, key, value);
        }

        /// <summary>
        ///     Removes all elements from the <see cref="OrderedListInternal{TKey,TValue}" />.
        /// </summary>
        public void Clear()
        {
            Array.Clear(_keys, 0, _size);
            Array.Clear(_values, 0, _size);
            _size = 0;
        }

        /// <summary>
        ///     Searches for the specified key and returns the zero-based index within the entire
        ///     <see
        ///         cref="OrderedListInternal{TKey,TValue}" />
        ///     .
        /// </summary>
        public int IndexOfKey(TKey key)
        {
            Should.NotBeNull(key, "key");
            int num = Array.BinarySearch(_keys, 0, _size, key, _comparer);
            if (num < 0)
                return -1;
            return num;
        }

        /// <summary>
        ///     Searches for the specified value and returns the zero-based index of the first occurrence within the entire
        ///     <see
        ///         cref="OrderedListInternal{TKey,TValue}" />
        ///     .
        /// </summary>
        public int IndexOfValue(TValue value)
        {
            return Array.IndexOf(_values, value, 0, _size);
        }

        public TKey GetKey(int index)
        {
            if (index >= _size)
                Thrower.IntOutOfRangeCollection("index");
            return _keys[index];
        }

        public TValue GetValue(int index)
        {
            if (index >= _size)
                Thrower.IntOutOfRangeCollection("index");
            return _values[index];
        }

        /// <summary>
        ///     Removes the element at the specified index of the <see cref="OrderedListInternal{TKey,TValue}" />.
        /// </summary>
        public void RemoveAt(int index)
        {
            if (index < 0 || index >= _size)
                Thrower.IntOutOfRangeCollection("index");
            --_size;
            if (index < _size)
            {
                Array.Copy(_keys, index + 1, _keys, index, _size - index);
                Array.Copy(_values, index + 1, _values, index, _size - index);
            }
            _keys[_size] = default(TKey);
            _values[_size] = default(TValue);
        }

        private void EnsureCapacity(int min)
        {
            int num = _keys.Length == 0 ? 4 : _keys.Length * 2;
            if (num < min)
                num = min;
            Capacity = num;
        }

        private int Insert(int index, TKey key, TValue value)
        {
            if (_size == _keys.Length)
                EnsureCapacity(_size + 1);
            if (index < _size)
            {
                Array.Copy(_keys, index, _keys, index + 1, _size - index);
                Array.Copy(_values, index, _values, index + 1, _size - index);
            }
            _keys[index] = key;
            _values[index] = value;
            ++_size;
            return index;
        }

        #endregion
    }

    /// <summary>
    ///     Represents a collection of objects that are sorted by key based on the associated
    ///     <see
    ///         cref="T:System.Collections.Generic.IComparer`1" />
    ///     implementation. Duplicate items (items that compare equal to each other) are allows in an OrderedListInternal.
    /// </summary>
    /// <typeparam name="T">
    ///     The type of item in the collection.
    /// </typeparam>  
#if WPF
    [Serializable]
#endif
    [DebuggerDisplay("Count = {Count}")]
    [DataContract(IsReference = true)]
    internal sealed class OrderedListInternal<T> : IList<T>, IList
    {
        #region Fields

        private static readonly T[] Empty = new T[0];
        private readonly IComparer<T> _comparer;
        private T[] _items;
        private int _size;
#if WPF
        [NonSerialized]
#endif
        [XmlIgnore]
        private object _syncRoot;

        #endregion

        #region Constructors

        /// <summary>
        ///     Initializes a new instance of the <see cref="OrderedListInternal{T}" /> class.
        /// </summary>
        public OrderedListInternal()
            : this(null)
        {
        }

        /// <summary>
        ///     Initializes a new instance of the <see cref="OrderedListInternal{T}" /> class.
        /// </summary>
        public OrderedListInternal(IComparer<T> comparer = null)
        {
            _size = 0;
            _items = Empty;
            if (comparer == null)
                comparer = Comparer<T>.Default;
            _comparer = comparer;
        }

        /// <summary>
        ///     Initializes a new instance of the <see cref="OrderedListInternal{T}" /> class.
        /// </summary>
        public OrderedListInternal(IEnumerable<T> items, IComparer<T> comparer = null)
            : this(comparer)
        {
            foreach (T item in items)
                Add(item);
        }

        #endregion

        #region Properties

        /// <summary>
        ///     Gets the comparer.
        /// </summary>
        public IComparer<T> Comparer
        {
            get { return _comparer; }
        }

        /// <summary>
        ///     Gets or sets the number of elements that the <see cref="OrderedListInternal{T}" /> can contain.
        /// </summary>
        public int Capacity
        {
            get { return _items.Length; }
            set
            {
                if (value == _items.Length)
                    return;
                if (value < _size)
                    Thrower.CapacityLessThanCollection("Capacity");
                if (value > 0)
                {
                    var keyArray = new T[value];
                    if (_size > 0)
                    {
                        Array.Copy(_items, 0, keyArray, 0, _size);
                    }
                    _items = keyArray;
                }
                else
                {
                    _items = Empty;
                }
            }
        }

        #endregion

        #region Methods

        public int GetInsertIndex(T item)
        {
            Should.NotBeNull(item, "item");
            int num = Array.BinarySearch(_items, 0, _size, item, _comparer);
            if (num >= 0)
                return num;
            return ~num;
        }

        private int IndexOfObject(T item)
        {
            return Array.IndexOf(_items, item, 0, _size);
        }

        private bool CheckInsertItem(T oldItem, T newItem, bool throwException = true)
        {
            if (Comparer.Compare(oldItem, newItem) != 0)
            {
                Should.BeValid("index", throwException);
                return false;
            }
            return true;
        }

        private int InsertInternal(int index, T item)
        {
            if (_size == _items.Length)
                EnsureCapacity(_size + 1);
            if (index < _size)
            {
                Array.Copy(_items, index, _items, index + 1, _size - index);
            }
            _items[index] = item;
            ++_size;
            return index;
        }

        private void EnsureCapacity(int min)
        {
            int num = _items.Length == 0 ? 4 : _items.Length * 2;
            if (num < min)
                num = min;
            Capacity = num;
        }

        #endregion

        #region Implementation of interfaces

        /// <summary>
        ///     Adds an item to the <see cref="T:System.Collections.IList" />.
        /// </summary>
        int IList.Add(object value)
        {
            Should.NotBeNull(value, "value");
            return Add((T)value);
        }

        /// <summary>
        ///     Determines whether the <see cref="T:System.Collections.IList" /> contains a specific value.
        /// </summary>
        bool IList.Contains(object value)
        {
            if (SyncronizedNotifiableCollection<T>.IsCompatibleObject(value))
                return Contains((T)value);
            return false;
        }

        /// <summary>
        ///     Removes all items from the <see cref="T:System.Collections.IList" />.
        /// </summary>
        void IList.Clear()
        {
            Clear();
        }

        /// <summary>
        ///     Determines the index of a specific item in the <see cref="T:System.Collections.IList" />.
        /// </summary>
        int IList.IndexOf(object value)
        {
            return IndexOf((T)value);
        }

        /// <summary>
        ///     Inserts an item to the <see cref="T:System.Collections.IList" /> at the specified index.
        /// </summary>
        void IList.Insert(int index, object value)
        {
            Insert(index, (T)value);
        }

        /// <summary>
        ///     Removes the first occurrence of a specific object from the <see cref="T:System.Collections.IList" />.
        /// </summary>
        void IList.Remove(object value)
        {
            if (SyncronizedNotifiableCollection<T>.IsCompatibleObject(value))
                Remove((T)value);
        }

        /// <summary>
        ///     Removes the <see cref="T:System.Collections.IList" /> item at the specified index.
        /// </summary>
        void IList.RemoveAt(int index)
        {
            RemoveAt(index);
        }

        /// <summary>
        ///     Gets or sets the element at the specified index.
        /// </summary>
        object IList.this[int index]
        {
            get { return this[index]; }
            set { this[index] = (T)value; }
        }

        /// <summary>
        ///     Gets a value indicating whether the <see cref="T:System.Collections.IList" /> is read-only.
        /// </summary>
        bool IList.IsReadOnly
        {
            get { return IsReadOnly; }
        }

        /// <summary>
        ///     Gets a value indicating whether the <see cref="T:System.Collections.IList" /> has a fixed size.
        /// </summary>
        bool IList.IsFixedSize
        {
            get { return false; }
        }

        /// <summary>
        ///     Copies the elements of the <see cref="T:System.Collections.ICollection" /> to an <see cref="T:System.Array" />,
        ///     starting at a particular <see cref="T:System.Array" /> index.
        /// </summary>
        public void CopyTo(Array array, int index)
        {
            Array.Copy(_items, 0, array, index, _size);
        }

        /// <summary>
        ///     Gets the number of elements contained in the <see cref="T:System.Collections.ICollection" />.
        /// </summary>
        int ICollection.Count
        {
            get { return Count; }
        }

        /// <summary>
        ///     Gets an object that can be used to synchronize access to the <see cref="T:System.Collections.ICollection" />.
        /// </summary>
        object ICollection.SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                    Interlocked.CompareExchange(ref _syncRoot, new object(), null);
                return _syncRoot;
            }
        }

        /// <summary>
        ///     Gets a value indicating whether access to the <see cref="T:System.Collections.ICollection" /> is synchronized
        ///     (thread safe).
        /// </summary>
        bool ICollection.IsSynchronized
        {
            get { return false; }
        }

        /// <summary>
        ///     Returns an enumerator that iterates through the collection.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < _size; i++)
                yield return _items[i];
        }

        /// <summary>
        ///     Returns an enumerator that iterates through a collection.
        /// </summary>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        ///     Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        void ICollection<T>.Add(T item)
        {
            Add(item);
        }

        /// <summary>
        ///     Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        public void Clear()
        {
            Array.Clear(_items, 0, _size);
            _size = 0;
        }

        /// <summary>
        ///     Determines whether the <see cref="T:System.Collections.Generic.ICollection`1" /> contains a specific value.
        /// </summary>
        public bool Contains(T item)
        {
            return IndexOfObject(item) != -1;
        }

        /// <summary>
        ///     Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1" /> to an
        ///     <see cref="T:System.Array" />, starting at a particular <see cref="T:System.Array" /> index.
        /// </summary>
        public void CopyTo(T[] array, int arrayIndex)
        {
            Array.Copy(_items, 0, array, arrayIndex, _size);
        }

        /// <summary>
        ///     Removes the first occurrence of a specific object from the
        ///     <see cref="T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        public bool Remove(T item)
        {
            Should.NotBeNull(item, "item");
            int indexOf = IndexOfObject(item);
            if (indexOf == -1)
                return false;
            RemoveAt(indexOf);
            return true;
        }

        /// <summary>
        ///     Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        public int Count
        {
            get { return _size; }
        }

        /// <summary>
        ///     Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1" /> is read-only.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        ///     Determines the index of a specific item in the <see cref="T:System.Collections.Generic.IList`1" />.
        /// </summary>
        public int IndexOf(T item)
        {
            Should.NotBeNull(item, "item");
            return IndexOfObject(item);
        }

        /// <summary>
        ///     Inserts an item to the <see cref="T:System.Collections.Generic.IList`1" /> at the specified index.
        /// </summary>
        public void Insert(int index, T item)
        {
            if (index > _size)
                Thrower.IntOutOfRangeCollection("index");                
            int insertIndex = GetInsertIndex(item);
            if (insertIndex == index)
            {
                InsertInternal(index, item);
                return;
            }
            if (index == 0 && _size == 0)
            {
                InsertInternal(index, item);
                return;
            }


            if (index == _size)
                CheckInsertItem(_items[_size - 1], item);
            else if (index == 0)
                CheckInsertItem(_items[0], item);
            else
            {
                if (!CheckInsertItem(_items[index], item, false) && !CheckInsertItem(_items[index - 1], item, false))
                    CheckInsertItem(_items[index + 1], item);
            }
            InsertInternal(index, item);
        }

        /// <summary>
        ///     Removes the <see cref="T:System.Collections.Generic.IList`1" /> item at the specified index.
        /// </summary>
        public void RemoveAt(int index)
        {
            if (index < 0 || index >= _size)
                Thrower.IntOutOfRangeCollection("index");                
            --_size;
            if (index < _size)
            {
                Array.Copy(_items, index + 1, _items, index, _size - index);
            }
            _items[_size] = default(T);
        }

        /// <summary>
        ///     Gets or sets the element at the specified index.
        /// </summary>
        public T this[int index]
        {
            get
            {
                if (index >= _size)
                    Thrower.IntOutOfRangeCollection("index");
                return _items[index];
            }
            set { Should.MethodBeSupported(false, "this[int index]"); }
        }

        /// <summary>
        ///     Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        public int Add(T item)
        {
            Should.NotBeNull(item, "item");
            return InsertInternal(GetInsertIndex(item), item);
        }

        #endregion
    }
}